% Ejercicio "Listas en Prolog"
\subsection*{\fbox{\theejercicio} - Listas en Prolog}

La siguiente gram\'atica corresponde a la fase sint\'actica del an\'alisis de algunas listas v\'alidas en Prolog:

\begin{center}
\begin{tabular}{|lcl|} \hline
                &               &                                         \\
{\em Lista}     & $\rightarrow$ & {\bf [ ]}                               \\
{\em Lista}     & $\rightarrow$ & {\bf [} {\em T\'ermino} {\bf ]}         \\
{\em T\'ermino} & $\rightarrow$ & {\em T\'ermino} {\bf ,} {\em T\'ermino} \\
{\em T\'ermino} & $\rightarrow$ & {\bf IDENTIFICADOR}                     \\
{\em T\'ermino} & $\rightarrow$ & {\em Lista}                             \\
                &               &                                         \\ \hline
\end{tabular}
\end{center}

Todas las series deben tener al menos un elemento.

\par Se pide:
\begin{enumerate}[1)]
\item Construir para esta gram\'atica las tablas de an\'alisis SLR(1).
\item Eliminar los posibles conflictos que aparecen en la tabla anterior, considerando que el operado `,' es asociativo por la izquierda.
\end{enumerate}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Apartado 1)

Para la gram\'atica ampliada

\begin{tabular}{llcl}
{\tt 1} & {\em Axioma}    & $\rightarrow$ & {\em Lista} {\bf \$}                    \\
{\tt 2} & {\em Lista}     & $\rightarrow$ & {\bf [ ]}                               \\
{\tt 3} & {\em Lista}     & $\rightarrow$ & {\bf [} {\em T\'ermino} {\bf ]}         \\
{\tt 4} & {\em T\'ermino} & $\rightarrow$ & {\em T\'ermino} {\bf ,} {\em T\'ermino} \\
{\tt 5} & {\em T\'ermino} & $\rightarrow$ & {\bf IDENTIFICADOR}                     \\
{\tt 6} & {\em T\'ermino} & $\rightarrow$ & {\em Lista}                             \\
\end{tabular}

obtenemos la tabla de an\'alisis SLR(1):

\begin{center}
TABLA DE ACCIONES

\begin{tabular}{|l|ccccc|} \hline
  & {\bf ID.} & {\bf ,} & {\bf [} & {\bf ]} & {\bf \$} \\ \hline
0 &           &         & D        &         &         \\
1 & D         &         & D        & D       &         \\
2 &           &         &          &         & $A_1$   \\
3 &           & $R_5$   &          & $R_5$   &         \\
4 &           & $R_2$   &          & $R_2$   & $R_2$   \\
5 &           & $R_6$   &          & $R_6$   &         \\
6 &           &  D      &          & D       &         \\
7 & D         &         & D        &         &         \\
8 &           & $R_3$   &          & $R_3$   & $R_3$   \\
9 &           & $R_4$/D &          & $R_4$   &         \\ \hline
\end{tabular}
\end{center}

\begin{center}
TABLA DE TRANSICIONES

\begin{tabular}{|l|ccccccc|} \hline
         & {\bf ID.} & {\bf ,} & {\bf [} & {\bf ]} & {\bf \$} & {\em Lista} & {\em Term.} \\ \hline
0        &           &         & 1       &         &          & 2           &             \\
1        & 3         &         & 1       & 4       &          & 5           & 6           \\
2        &           &         &         &         &          &             &             \\
3        &           &         &         &         &          &             &             \\
4        &           &         &         &         &          &             &             \\
5        &           &         &         &         &          &             &             \\
6        &           & 7       &         & 8       &          &             &             \\
7        & 3         &         & 1       &         &          & 5           & 9           \\
8        &           &         &         &         &          &             &             \\
9        &           &         & 7       &         &          &             &             \\ \hline
\end{tabular}
\end{center}

Apartado 2)

En el estado 9, con el s\'{\i}mbolo `,', se produce un conflicto que se resuelve usando siempre reducci\'on, y no el desplazamiento. Ya que el operador debe ser asociativo por la izuquierda, debemos reducir con \'el tan pronto como sea posible al ser lectura de izquierda a derecha.